<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Linear Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="libman008.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman002.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman010.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc14">1.7</A>&nbsp;&nbsp;Linear Constraints</H2><UL>
<LI><A HREF="libman009.html#toc7">External Linear Solvers: <EM>eplex</EM></A>
<LI><A HREF="libman009.html#toc8"><EM>clpqr</EM></A>
<LI><A HREF="libman009.html#toc9">Piecewise Linear: <EM>eplex_relax</EM></A>
<LI><A HREF="libman009.html#toc10">Probing for Scheduling</A>
</UL>

There are two libraries supporting linear constraint solving. The
first <EM>eplex</EM> provides an interface to external linear
programming packages. 
It offers flexibility and scalability, but may
require a license for the external software.
The second <EM>clpqr</EM> can support infinite precision, but is less
efficient and scalable and offers fewer facilities.<BR>
<BR>
<A NAME="toc7"></A>
<H3 CLASS="subsection"><A NAME="htoc15">1.7.1</A>&nbsp;&nbsp;External Linear Solvers: <EM>eplex</EM></H3>
<EM>eplex</EM> supports a tight integration [<A HREF="libman072.html#Bockmayr"><CITE>3</CITE></A>] between
external linear solvers (CPLEX [<A HREF="libman072.html#ILOG"><CITE>12</CITE></A>] and XPRESS [<A HREF="libman072.html#Dash"><CITE>19</CITE></A>])
and ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>. 
Constraints as well as variables can appear in both the external
linear solver and other ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>  solvers.
Variable bounds are automatically passed from the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>  <EM>range</EM>
solver to the external solver.
Optimal solutions and other solutions can be returned to ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>  as
required.
Search can be carried out either in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>  or in the external solver.<BR>
<BR>
<A NAME="toc8"></A>
<H3 CLASS="subsection"><A NAME="htoc16">1.7.2</A>&nbsp;&nbsp;<EM>clpqr</EM></H3>
The <EM>clpqr</EM> library offers two implementations of the Simplex
method for solving linear constraints [<A HREF="libman072.html#Holzbauer"><CITE>11</CITE></A>]. 
One version uses rationals and
is exact. The other version uses floats.
This library employs public domain software, and can be used for small
problems (with less than 100 variables).<BR>
<BR>
<A NAME="toc9"></A>
<H3 CLASS="subsection"><A NAME="htoc17">1.7.3</A>&nbsp;&nbsp;Piecewise Linear: <EM>eplex_relax</EM></H3>
This library handles any user-defined piecewise linear function as a
constraint closely integrated with <EM>eplex</EM>. It offers better
pruning than the standard handling of piecewise linear constraints
in the external solvers [<A HREF="libman072.html#Ajili"><CITE>1</CITE></A>].<BR>
<BR>
<A NAME="toc10"></A>
<H3 CLASS="subsection"><A NAME="htoc18">1.7.4</A>&nbsp;&nbsp;Probing for Scheduling</H3>
For scheduling applications where the cost is dependent on each start
time, a combination of solvers can be very powerful.
For example, we can use finite domain
propagation to reason on 
resources and linear constraint solving to reason on cost [<A HREF="libman072.html#HaniProbe"><CITE>4</CITE></A>].<BR>
<BR>
The <EM>probing_for_scheduling</EM> library supports such a combination,
via a similar user interface to the <EM>cumulative</EM> constraint mentioned
above.<BR>
<BR>
<HR>
<A HREF="libman008.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman002.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman010.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
